﻿#include <iostream>

//Pow（x, n） - 快速幂（medium）
class Solution {
public:
    double myPow(double x, int n) {
        return n > 0 ? Pow(x, n) : 1 / Pow(x, -(long long)n);
    }
    double Pow(double x, int n)
    {
        if (n == 0)
            return 1;
        double tmp = Pow(x, n / 2);
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }

};  

//2331.计算布尔⼆叉树的值
class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        if (root == nullptr)
            return true;
        if (root->val == 1)
            return true;
        if (root->val == 0)
            return false;
        bool left = evaluateTree(root->left);
        bool right = evaluateTree(root->right);
        bool result;
        if (root->val == 2)
        {
            result = left | right;
        }
        if (root->val == 3)
        {
            result = left & right;
        }
        return result;
    }
};

class Solution {
    long prev = LONG_MIN;
public:
    bool isValidBST(TreeNode* root) {
        if (root == nullptr)
            return true;
        bool left = isValidBST(root->left);
        if (left == false) return false;
        bool cur = false;
        if (root->val > prev)
            cur = true;
        prev = root->val;
        if (cur == false) return false;
        bool right = isValidBST(root->right);
        if (cur == false) return false;
        return left && right && cur;
    }

};
class Solution {

public:
    static int ret;
    static int count;
    int kthSmallest(TreeNode* root, int k) {
        count = k;
        dfs(root);
        return ret;
    }
    void dfs(TreeNode* root)
    {
        if (root == nullptr)
            return;
        dfs(root->left);
        count--;
        if (count == 0)
        {
            ret = root->val;
            return;
        }
        dfs(root->right);
    }
};
